//给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。 
//
// 
//
// 示例 1： 
//
// 
//输入: root = [8,6,10,5,7,9,11], k = 12
//输出: true
//解释: 节点 5 和节点 7 之和等于 12
// 
//
// 示例 2： 
//
// 
//输入: root = [8,6,10,5,7,9,11], k = 22
//输出: false
//解释: 不存在两个节点值之和为 22 的节点
// 
//
// 
//
// 提示： 
//
// 
// 二叉树的节点个数的范围是 [1, 10⁴]. 
// -10⁴ <= Node.val <= 10⁴ 
// root 为二叉搜索树 
// -10⁵ <= k <= 10⁵ 
// 
//
// 
//
// 注意：本题与主站 653 题相同： https://leetcode-cn.com/problems/two-sum-iv-input-is-a-bst/
// 
//
// Related Topics 数组 滑动窗口 👍 71 👎 0


package LeetCode.editor.cn;


import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author ldltd
 * @date 2025-02-19 19:56:08
 * @description LCR 056.两数之和 IV - 输入二叉搜索树
 
 */
 
public class OpLdQZ {
    public static void main(String[] args) {
    //测试代码
    OpLdQZ fun = new OpLdQZ();
    Solution solution= fun.new Solution();
    
    }

//leetcode submit region begin(Prohibit modification and deletion)

//  Definition for a binary tree node.
  public class TreeNode {
      int val;
      TreeNode left;
     TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
  }

class Solution {
        //法1.广度或者深度搜索+hash表，每个节点路过了，存入target-node.val
        //法2.遍历完之后，保存到有序数组中，按有序数组处理，需要on空间
        // 如果是一个正常的有序数组，用双指针，在首尾压缩到合适的位置即可
        //所以问题变成了如何在搜索二叉树上使用双指针压缩
        //用栈维护左右指针，先存入栈中，就可以O1取出，但是其实和遍历一样
        public boolean findTarget(TreeNode root, int k) {
            TreeNode left = root, right = root;
            Deque<TreeNode> leftStack = new ArrayDeque<TreeNode>();
            Deque<TreeNode> rightStack = new ArrayDeque<TreeNode>();
            leftStack.push(left);
            while (left.left != null) {
                leftStack.push(left.left);
                left = left.left;
            }
            rightStack.push(right);
            while (right.right != null) {
                rightStack.push(right.right);
                right = right.right;
            }
            while (left != right) {
                if (left.val + right.val == k) {
                    return true;
                }
                if (left.val + right.val < k) {
                    left = getLeft(leftStack);
                } else {
                    right = getRight(rightStack);
                }
            }
            return false;
        }

    public TreeNode getLeft(Deque<TreeNode> stack) {
        TreeNode root = stack.pop();
        TreeNode node = root.right;
        while (node != null) {
            stack.push(node);
            node = node.left;
        }
        return root;
    }

    public TreeNode getRight(Deque<TreeNode> stack) {
        TreeNode root = stack.pop();
        TreeNode node = root.left;
        while (node != null) {
            stack.push(node);
            node = node.right;
        }
        return root;
    }

}
//leetcode submit region end(Prohibit modification and deletion)

}
